/*
 * @lc app=leetcode id=30 lang=cpp
 *
 * [30] Substring with Concatenation of All Words
 */
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int len = s.size();
        int wnum = words.size();

        if (len < 1 || wnum < 1) {
            return ret;
        }

        int wlen = words[0].size();
        int sublen = wlen*wnum;

        unordered_map<string, int> memo;
        for (auto s : words) {
            memo[s]++;
        }

        for (int i=0; i<len-sublen+1; i++) {
            int num = 0;
            unordered_map<string, int> hasWords;

            while (num < wnum) {
                string word = s.substr(i+wlen*num, wlen);
                if (memo.find(word) != memo.end()) {
                    hasWords[word]++;
                    if (hasWords[word] > memo[word]) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }

            if (num == wnum) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};

